#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int change(int amount, vector<int> &coins)
    {
        vector<int> dp(amount + 1, -1);
        dp[0] = 1;
        return dfs(amount, dp, coins);
    }

    int dfs(int amount, vector<int> &dp, vector<int> &coins)
    {
        if (amount < 0)
            return 0;
        if (dp[amount] != -1)
            return dp[amount];
        dp[amount] = 0;
        for (int coin : coins)
        {
            if (amount >= coin)
            {
                int ret = dfs(amount - coin, dp, coins);
                dp[amount] += ret;
            }
        }
        return dp[amount];
    }
};

int main()
{
    cout << "Code518" << endl;
    Solution s;
    vector<int> coins = {1, 2, 5};
    cout << s.change(5, coins) << endl;
    return 0;
}